#include <stdio.h>

// 二分查找，返回找到的位置
int bi_search(int key, int A[], int low, int high) {
    //直接利用参数做变量，high应为最大索引而非个数.
    while (low <= high)
    {
        // 折半，算中间位置
        // 移位作除以2,c语言此计算会向下取整.
        int mid = (low + high) >> 1; 
        // 比较此位置
        if (key == A[mid])
        {
            return mid;
        } 
        // 中间位置不是，更新区间
        else if(key < A[mid])
            // 或在前面，high挪到mid处（mid前一位置）
            high = mid - 1;
        else
            // 或在后面，low应挪到mid处（mid后一位置）
            low = mid + 1;
    }
    // 未找到，返回无效索引.
    return -1;
}


// 二分查找-递归法，返回找到的位置
int bi_search_recursively(int key, int A[], int low, int high) {
    while (low <= high)
    {
        // 折半，算中间位置
        int mid = (low + high) >> 1; 
        // 比较此位置
        if (key == A[mid])
        {
            return mid;
        } 
        // 中间位置不是，更新区间
        else if(key < A[mid])
            // 或在前面，high挪到mid处（mid前一位置）
            return bi_search_recursively(key, A, low, mid - 1);
        else
            // 或在后面，low应挪到mid处（mid后一位置）
            return bi_search_recursively(key, A, mid+1, high);
    }
    // 未找到，返回无效索引.
    return -1;
}

int main()
{
    int A[] = {5,16,20,27,30,36,44,55,60,67,71};
    int n = sizeof(A) / sizeof(int);

    for (int k = 0; k < n; ++k) {
        int p = bi_search_recursively(A[k], A, 0, n - 1);
        printf("search %d@%d at %d\n", A[k], k, p);
    }
}